<?php
/**
 * consistent hash is way to solve messing up 
 * items problem whan 1 server deleted from cluster
 * 
 * if 1 server deleted than all other objects will stay on same servers
 * 
 * example of usage:
 * 
 * to remove server from pool just make item empty, 
 * by this way all cached items will not be reorganized, 
 * only keys from removed server will be reorganized
 * 
 * 
 * $servers = array(
										'server1',
										'server2',
										'server3',
									 );
	$objCHash = new ConsistentHash($servers);	
	$host = $objCHash->Lookup($id_of_object,3);
	
										 
 * 
 * @author Magic
 *
 */

class ConsistentHash{
	public $Circle = array();
	public $CircleKeys = array();
	public $Points = 64;
	public function __construct($servers,$points=64){
		$this->Points = $points;
		$this->addToCircle($servers);
		
	}
	
	/**
	 * add all existing servers to integer circle
	 * @param $servers
	 * @return bool
	 */
	public function addToCircle($servers){
		$max_val = 4294967296;
				   
		$total_weight = 0;
		$weight = $this->Points;
		$server_count = count($servers);
		$total_weight = $server_count*$weight;
		
		// numbers of points in circle
		$grow = round($max_val/$total_weight);
		
		$j = 0;
		
		for ($i=0; $i <=$max_val; $i+=$grow){
			if ($servers[$j]){
				$circle[sprintf('%u',$i)] = $servers[$j];
			}
			$j<$server_count-1?$j++:$j=0;		
		}
		
		ksort($circle);
		reset($circle);
		$this->Circle = $circle;
		//print_r($this->Circle); die;
		
		$this->CircleKeys = array_keys($circle);
		
		return true;
	}
	
	/**
	 * search needed point in circle
	 * return index of element in circle
	 * uses binary search method. 
	 * 
	 * if $pointsCount = 1 than will be returned string, 
	 * if $pointsCount >1 than will be returned array of strings
	 * 
	 * usually you not need cahnge here anything
	 * 
	 * @param $search_val
	 * @param $pointsCount
	 * @return int
	 */
	private function searchInCircle($search_val,$pointsCount=1){
		//$search_val = $search_val;
		$circle_keys = $this->CircleKeys;

		$circle_count = count($circle_keys);
		$res = false;
		$i = $circle_count-1;
		
		// { here we looking key not in circle. rule: max>key<0 - key is out of circle
		// this key will be associated with fist or last item in circle
		if ($circle_keys[$i]<=$search_val && $search_val<=$circle_keys[0]){
			//found
			if ($search_val-$circle_keys[$i]<$circle_keys[0]-$search_val){
				$res = $circle_keys[$i];
			}else{
				$res = $circle_keys[0];
			}
			return $res;
		}elseif($circle_keys[$i]<=$search_val){
			$res = $circle_keys[$i];
		}elseif($search_val<=$circle_keys[0]){
			$res = $circle_keys[0];
		}
		// }
		
		// { if key in circle than search it in circle
		// uses binary searching algorithm
		if (!$res){
			$i=floor(($circle_count-1)/2); 
			$distance = $circle_count-1-$i;
			while(true){
				if ($circle_keys[$i]<=$search_val && $search_val<=$circle_keys[$i+1]){
					//found
					if (abs($search_val-$circle_keys[$i])<abs($circle_keys[$i+1]-$search_val)){
						$res = $circle_keys[$i];
					}else{
						$res = $circle_keys[$i+1];
						$i+=1;
					}
					break;
				}else{
					$distance = floor($distance/2);
					$distance = $distance>0?$distance:1;
					if ($search_val>$circle_keys[$i+1]){
						$i = $i + $distance;
					}else{
						$i = $i - $distance;
					}
				}
			}
		}		
		// }	
		$result = $res;
		// { search another nearly items, 
		// this can be need in case if found items not avaiable at some reason 
		// and program should try another item
		if ($pointsCount>1){ 
			$result = array($res);
			$_l = 1; // go left index
			$_r = 1; // go right index
			for ($j=1; $j<$pointsCount; $j++){
				if (abs($search_val-$circle_keys[$i-$_l])<abs($circle_keys[$i+$_r]-$search_val)){
					$result[] = $circle_keys[$i-$_l];
					$_l++;
				}else{
					$result[] = $circle_keys[$i+$_r];
					$_r++;
				}
			}
		}
		// }
		
		return $result;
	}
	/**
	 * will return constant server name for constant data
	 * each data will be saved on own server, so there 
	 * will not be mixed data in claster
	 * 
	 * if $pointsCount = 1 than will be returned string, 
	 * if $pointsCount >1 than will be returned array of strings
	 * 
	 * @param $data
	 * @param $pointsCount
	 * @return mixed
	 */
	public function Lookup($data,$pointsCount=1){
		return $this->getHost($this->Hash($data),$pointsCount);
	}
	
	/**
	 * just hash data by crc32
	 * 
	 * @param $data
	 * @return unknown_type
	 */
	public function Hash($data){
		return sprintf('%u',crc32($data));
	}
	
	
	/**
	 * returns server|servers by hashed key
	 * @param $key
	 * @param $pointsCount
	 * @return mixed
	 */
	public function getHost($key, $pointsCount = 1){
		$res = $this->searchInCircle($key,$pointsCount);
		if (is_array($res)){
			$result= array();
			foreach ($res as $v){
				if (!in_array($this->Circle[$v],$result)){
					$result[] = $this->Circle[$v]; 
					//$result[] = $v; 
				}
			}
		}else{
			return $this->Circle[$res];	
		}
		
		return $result;
	}
}